#include "sort.h"

// 打印数组
void print_arr(int *arr, int len_arr)
{
    int i;
    for(i=0;i<len_arr;++i){
        cout << *(arr+i) << " ";
    }
    cout << "\n";
}
// 冒泡排序
void bubble_sort(int *arr, int len_arr)
{
    print_arr(arr, len_arr);
    int i,j,n=len_arr-1,temp=0;
    for(i=0;i<n;++i){
        for(j=0;j<n-i;++j){
            // 由小到大
            if(arr[j]>arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        print_arr(arr,len_arr);
    }
}
// 选择排序
void selection_sort(int *arr, int len_arr)
{
    print_arr(arr, len_arr);
    int i,j,n=len_arr-1,min_idx;
    for(i=0;i<n;++i){
        min_idx = i;
        for(j=i+1;j<len_arr;++j){
            if(arr[j]<arr[min_idx])
                min_idx = j;            // 交换下标
        }
        // 如果有比i更小的才交换
        if(min_idx != i){
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
        print_arr(arr,len_arr);
    }
}
// 插入排序
void insertion_sort(int *arr, int len_arr) {
    print_arr(arr, len_arr);
    int i, j, key;
    for (i = 1; i < len_arr; i++) {  // 修正：i < len_arr（不是 len_arr - 1）
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j+1] = key;  // 修正：arr[j + 1] = key（不是 arr[j]）
        print_arr(arr, len_arr);
    }
}
